The invention deals with development of novel, efficient genetic algorithms in order to solve bi-objective optimization problems (BOOPs). Multi-objective optimization problems (MOOPs) are deconstructed into multiple BOOPs, which are further deconstructed into multiple single-objective optimization problems (SOOPs).
Genetic algorithms are in a class of computational metaheuristics that solve optimization problems. By decomposing MOOPs, which appear in various engineering and computational domains, into BOOPs, complex combinatorial optimization problems become solvable.
Several classes of metaheuristics have been used to solve optimization problems. These include local search metaheuristics (tabu search, scatter search and adaptive memory programming), global search metaheuristics (Monte Carlo and simulated annealing), swarm intelligence metaheuristics for local and neighborhood search (ant colony optimization, particle swarm optimization and stochastic diffusion search) and artificial immune systems metaheuristics. In general, these metaheuristic models involve learning processes made possible by the combination of memory and evolution. The metaheuristics are shortcuts for finding rapid solutions to optimization problems.
The local search metaheuristics develop an initial solution by relying on a short-term memory (although adaptive memory programming uses long-term memory), limited search constraints and a constant updating of the memory catalogue of objects that are learned in the heuristic process. Global search metaheuristics are generalized stochastic random processes for solving optimization problems. Swarm intelligence metaheuristics utilize collective memory and reinforcement learning from multiple agents to create a model for solving optimization problems.
Local Search Models
Developed by Glover, the tabu search (TS), scatter search (SS) and adaptive memory programming (AMP) models use similar search strategies to access a memory, reprogram the memory with new information obtained in the search process and guide the search process by accessing a catalogue created by the memory updating process. The combination of memory and evolutionary progression create a learning process.
Tabu Search
The TS metaheuristic uses a local or neighborhood search process to interactively move from one solution to a modified solution until a specific constraint has been satisfied. As the search progresses, information is excluded that guides the process to search space that is increasingly probable to achieve success in solving a problem. TS uses short-term memory structures in order to access a tabu list that contains solutions to problems that have been visited in the recent past. Solutions from the tabu list are excluded from the new search. Further, the tabu list can be overridden by using “aspiration criteria” so as to allow better solutions than are currently available.
TS methods use “inhibition” to exclude criteria and continuously filter the search space. The memory elements of the tabu process are updated from the past search results so as to limit the forward search space to non-redundant locations. This model increases efficiency in local or neighborhood search as it creates a pattern of development. This is a form of subtractive or exclusionary analysis that filters search space that has already been determined not to contain the desired solution.
A simple analogy to TS would be the search and rescue of a hiker or swimmer. In a static environment, the search party will cover a terrain and not return there because doing so would be redundant and inefficient. In order to keep track of the terrain they covered, the search party keeps a checklist of specific spaces and marks off the spaces after they have been searched. This process narrows the search over time, increases the likelihood of finding the hiker or swimmer and conserves scarce resources.
The exclusionary model of TS has limits. First, there are limits to the development of the initial catalogue based on an arbitrary local search. That is, the initial construction of a catalogue accessed in updatable memory is arbitrary. Second, since this initial position is arbitrary, the pattern of search is random as well, a further inefficiency. Third, the memory process is limited to the past, which is conditioned upon the arbitrary and random evidence obtained in the search process at a particular time. Fourth, the TS model is limited by the timing of the updating process. This limitation represents an arbitrary cross-section of time, which constrains the process to a static search space. Specifically, TS is not effective in an evolving environment with changing conditions unless the catalogue is continuously updated to reflect the reinvestigation of space that was subsequently covered under specific conditions.
Scatter Search
The SS method is an evolutionary approach that joins solutions based on a “generalized path” between two previous initial solutions. A reference set of two points in a search space is connected to create a new solution. The chief way to create the initial solutions is to combine linear points representing two solutions. The initial reference set then evolves in such a way that the new solutions are incorporated into the updated reference set for locating future solutions and so on.
SS uses several components in an evolutionary process: (a) Diversification generation method, (b) improvement method, (c) reference set update method, (d) subset generation method and (e) solution combination method. After the SS method generates a starting set of solution vectors, it then creates new points from linear combinations of subsets of current reference points. Finally, it extracts a collection of the best points from the previous phase as starting points for new applications of the heuristic process of the later phase.
There are limitations to the SS metaheuristic model. First, SS merely seeks averages of arbitrary initial search space. Second, the local arbitrary averaging is generalized and reinforced. This model is inefficient unless it can be continuously optimized by updating its reference set. Next, there are limits to the timing of the updating of the catalogue. Finally, this model is particularly limited in environments that are evolving in which it is required to revisit previously searched space.
The AMP model of a generalized search approach overcomes some of the limits of TS and SS. AMP utilizes a longer term memory and a neighborhood search space. Still, AMP suffers from some of the limits of the local search metaheuristics. Additional local search models, including GRASP, suffer from the same constraints of local search space optimization methods.
Swarm Intelligence Metaheuristics
Ant colony optimization (ACO) techniques, particle swarm optimization (PSO) and stochastic diffusion search (SDS) models use neighborhood search approaches to solve optimization problems. The biologically-inspired model of swarm intelligence uses the collective behavior of cooperating insects.
Ant Colony Optimization
Developed by Dorigo, following the work of Wilson, ACO techniques rely on ant collective behaviors for inspiration to develop a cooperating model of solving optimization problems. For example, ants use pheromones, a chemical substance that is emitted and detected, to guide behaviors. Computational emulation of this type of process in ant collective behaviors allows a limited intelligence to emerge that solves optimization problems. Reinforcement learning occurs via use of the pheromone deposition strategy, which emulates an externally accessible memory system. The pheromone system is self-reinforcing in the sense that it increases with more use and decreases with less use. The ACO process is adaptive to environmental change but relies on the combined efforts of multiple agents that interact in a local or neighborhood space.
One particular use of the ACO is development of work-arounds for bottlenecks. In the case of actual ant colony operation, if a piece of food is obstructed, ants will find a way around the obstruction and reinforce this pathway.
ACO has limits. It is limited to locally obtained information. Specifically, the most recent data are reinforced, rather than the correct data. The initial set of data is arbitrary and risks running the ant agents into blind, and inefficient, alleys that squander scarce resources. In effect, the ACO translates a quantity of inputs into intensity; however, if the source of the initial, random quantity is inefficient, the whole system will be inefficient. The system lacks a way to minimize its losses. Ultimately, this model will find solutions to optimization problems under constraints, but its learning model is solipsistic and circular.
Particle Swarm Optimization
The logic of swarm behaviors is to avoid neighbors while also following a leader, even as the leadership role changes at key thresholds. Within this changed leadership, the initiation process is asymmetric. Like ACO, the PSO metaheuristic uses local and neighborhood search techniques which rely on the interactive behaviors of neighboring agents. In the case of PSO, the model uses a universal access memory because any agent can access the behavior of other agents in the swarm configuration at a specific time.
One of the key objectives of PSO is identification of the conditions that allow a leader to change in the swarm. The asymmetric effects of PSO behaviors provide a random search process. The memory register of the swarm is generalized as the system accesses information from the behaviors of all of the collective's membership. However, the positioning of particular members is restricted to specific actions relative to the positions of other agents in the swarm.
Stochastic Diffusion Search
SDS blends aspects of ACO and PSO by allowing one-to-one direct communication between agents. In SDS, a sub-group of agents in the general collective test and optimize initial solutions which behave as hypotheses for future potential actions. Agents perform a preliminary evaluation and generate a candidate solution to a search problem. However, agents share information about these hypotheses, which illustrates how the diffusion model operates directly (one-to-one) between agents. High quality solutions can be generated from groups of interacting agents by using the hypotheses.
Like the PSO, SDS is limited to local and neighborhood search because the agents need to communicate with each other directly. Again, the initial hypothesis is arbitrary and may misdirect the group, thus providing an inefficient start of a search process. As feedback is provided to update the hypotheses, the system learns, but the learning occurs only within the context of specifically interacting agents in real time. If the environment changes, the earlier hypotheses become obsolete.
General Metaheuristics
Global search heuristics include Monte Carlo and simulated annealing models. These models generally breed randomized variations within a defined range to create a model to solve optimization problems.
An additional category of metaheuristics uses the human immune system as guidance to create an artificial immune system (AIS). AISs are computationally emulated learning models that imitate the operation of the immune system's humoral and adaptive subsystems in order to develop a defense against a new pathogen and then, once learned, to pass on the new immunity to a new generation for rapid defense against a known pathogen.
Glover also developed a surrogate constraint method for solving a class of optimization problems.
Genetic Algorithms
Holland developed a way to emulate the process of evolution in order to solve optimization problems. Genetic algorithms (GAs) create numerous generations by emulating sexual reproduction and random mutations in order to create later generations that are fit enough to match an environment and thus present adequate solutions to complex problems.
By emulating the genetic model in nature, GAs perform specific functions that allow organisms to better fit their environment and thereby gain a competitive advantage to survive. The most fit organism reinforces its competitive advantage and passes on its genes to future generations.
A problem with traditional GA is that its evolution relies only on random crossover and random mutation. In some cases, many thousands of generations of evolution are necessary in order to identify a solution, which is time consuming and inefficient. While the evolutionary process of the GA develops in order to solve problems of matching fitness of a strong group with an environment, as the environment itself evolves, the evolutionary process must continue to develop. Identifying co-evolutionary processes at worst is arbitrary and at best develops a solipsistic equilibrium in a static environment. Finally, because the environment changes in unpredictable ways, and because the GA development process is past-solution based, it is unable to offer predictions of future possible optimal fitness of the environment. This makes GA ineffective for solving problems in crisis periods of rapid or volatile environmental change.
Unlike the local search or swarm intelligence models, GA lacks a “memory” and must be constantly compared at each new generation to the fitness of the environment. In this sense, the environmental feedback is instantaneous.
These GA limitations are overcome by combining them with other metaheuristics techniques to create hybrid metaheuristics. By combining elements of positive-inclusive metaheuristics (ACO, PSO and SDS) with negative-exclusionary metaheuristics (TS, SS and AMP), the present hybrid GA metaheuristic is able to develop learning capabilities and to successfully solve problems. Such a hybrid GA model will reject unsuccessful solution attempts, re-focus on and accelerate successful solution attempts and develop positive reinforcement based on initial success.
The present system provides a range of new methods for improving GA and for creating novel hybrid metaheuristics using GA. By removing some of the GA constraints of (a) randomness, (b) ever-present environmental fitness criteria and (c) memory, the present system provides a radical alternative that is able to develop a learning heuristic that efficiently solves bi-objective optimization problems. Learning is seen as a byproduct of the combination of several key elements, including memory and evolution, in a hybrid GA metaheuristic. The adaptation made possible by the application of learning solves complex optimization problems.
Bi-Objective Optimization Problems
Solving optimization problems involves finding the best results within specific constraints. Many engineering optimization problems are very complex and involve the need to solve problems with multiple constraints. In order to build a successful car, for instance, a manufacturer needs a design that is stylish but also fuel efficient, safe and economically priced. These multiple constraints provide substantial engineering challenges.
In order to increase the chances of success in finding solutions, multi-objective optimization problems (MOOPs) are broken down into their simplest elements. The simplest combinatorial optimization problems are bi-objective optimization problems (BOOPs) that balance two constraints. Single objective optimization problems (SOOPs) do not capture the “compromise” between key constraints necessary to solve BOOPs. BOOPs are the significant unit in optimization problems, upon which MOOPs are built. Multiple variables and constraints can be deconstructed to the most elemental BOOP in order to assess sets of solution space options.
A major challenge in solving BOOPs by using metaheuristic techniques is to identify ways to obtain global information in a local search environment. Since BOOPs are the simplest type of combinatorial optimization problem, the issue of moving from one to two opposing goals involves balancing objectives. Metaheuristic techniques have been valuable in solving different classes of optimization problems because of the ability of the learning mechanism, via the use of memory and evolution, to delimit specific constraints over time in order to identify the best options from among a set of solution candidates.
An example of a SOOP is finding the shortest path. This minimization optimization search space involves finding solutions within a field of options with limited constraints. When an additional set of constraints is introduced, as in the case of BOOPs, the conflict arises in which a single option is impossible; rather, the solution space involves locating multiple optimization options, or a family of solutions. The best-available solution involves selecting specific combinations of solutions within limited constraints. These sets of possible solutions refer to probable combinations that represent a compromise between extreme SOOP constraints.
While the minimization search problem epitomizes the SOOP, the allocation problem epitomizes the BOOP. The aim is to find the fewest resources necessary to satisfy a set of constraints. An example of the allocation problem involves scheduling, in which priorities are made over at least two points of time. The traveling salesman problem (TSP) represents a sort of BOOP. The greatest benefit of solving BOOPs is that they define the resources needed to most efficiently proceed with a particular set of goals.
In communications systems, for example, BOOPs are applied to bandwidth resource constraints, load balancing, path optimization and goal prioritization problems. In general, in computer systems, the simplest or earliest problem is solved, then the more complete problem is solved. The BOOP is a central element of optimization problems that leads to different levels of solutions for more complex optimization problems.
GAs maintain a pool of solutions, rather than a single solution. By mimicking biological evolution, the GA finds superior sets of solutions over time. The solution options are randomly combined or mutated to alter the composition of the pool of solutions. Inferior solutions, as measured by the real-time environmental fitness criterion, are discarded.
GAs as presently conceived, however, are limited in their ability to solve BOOPs efficiently. Precisely because they rely on random combinations and mutations and are compared with a present environmental fitness criterion, they provide narrow and somewhat inefficient solution options. Ironically, they lack an evolutionary character that accommodates the evolving solutions needed within a changing environment. Since they are restricted to past-oriented generations, they do not build new solutions to evolving problems. Since they lack memory capacities, they also lack the learning functions of other metaheuristics. Consequently, there is a tendency to repeat past solutions, which fail to solve new problems in a time-sensitive way.
What is needed to solve BOOPs in a complex evolving environment is a hybrid of GA and other metaheuristics techniques. The hybrid GA metaheuristic technique disclosed in the present invention is efficient, on-demand and flexible. In the short-run, it provides adequate solutions to BOOPs that allow more solutions to be offered to more complex combinatorial optimization problems. Overall, the present invention develops a system in which global information is made available to local search behaviors in order to increase efficiency of combinatorial optimization problem solving procedures.
In order to develop an effective and efficient GA metaheuristic, the critical functions of crossover and mutation need to be reexamined and refined. The present system offers methods to perform these functions.
There is a range of information technology, computer science and engineering systems to which the present system applies. The present system solves optimization problems involving computing, communications and robotics.